package data_structure;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class leetcode_0264 {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>(new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return o1.compareTo(o2);
            }
        });
        priorityQueue.add(1L);
        Set<Long> set = new HashSet<>();
        set.add(1L);
        Long result =1L;
        while (n != 0) {
            result = priorityQueue.poll();
            n = n - 1;
            if(!set.contains(2*result)){
                set.add(2*result);
                priorityQueue.add(2*result);
            }
            if(!set.contains(3*result)){
                set.add(3*result);
                priorityQueue.add(3*result);
            }
            if(!set.contains(5*result)){
                set.add(5*result);
                priorityQueue.add(5*result);
            }
        }
        return result.intValue();
    }
}
